import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 不用递归，用迭代的方式实现二叉树的三序遍历
public class BinaryTreeTraversalIteration {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 先序打印所有节点，非递归版
    public static void preOrder(TreeNode head) {
        // 如果根节点不为空，则进行先序遍历
        if (head!= null) {
            // 创建一个存储TreeNode类型的栈，用于辅助实现先序遍历
            Stack<TreeNode> stack = new Stack<>();
            // 将根节点压入栈中，这是先序遍历首先访问根节点的体现
            stack.push(head);
            // 只要栈不为空，就继续进行遍历操作
            while (!stack.isEmpty()) {
                // 弹出栈顶元素，这个元素将被访问，并将其赋值给head变量（这里主要是为了后续操作方便）
                head = stack.pop();
                // 输出当前节点的值，这是先序遍历中访问节点的操作
                System.out.print(head.val + " ");
                // 如果当前节点的右子节点不为空，则将右子节点压入栈中
                // 由于栈的后进先出特性，右子节点会在左子节点之后被访问，符合先序遍历（根 - 左 - 右）的顺序
                if (head.right!= null) {
                    stack.push(head.right);
                }
                // 如果当前节点的左子节点不为空，则将左子节点压入栈中
                // 左子节点会先于右子节点被访问，符合先序遍历的顺序
                if (head.left!= null) {
                    stack.push(head.left);
                }
            }
            // 在完成整棵树的遍历后，换行，使输出更美观
            System.out.println();
        }
    }



    // 中序打印所有节点，非递归版
    public static void inOrder(TreeNode head) {
        // 如果根节点不为空，则进行中序遍历
        if (head!= null) {
            // 创建一个存储TreeNode类型的栈，用于辅助实现中序遍历
            Stack<TreeNode> stack = new Stack<>();
            // 只要栈不为空或者当前节点head不为空，就继续循环
            while (!stack.isEmpty() || head!= null) {
                // 如果当前节点head不为空
                if (head!= null) {
                    // 将当前节点压入栈中，这是因为中序遍历需要先访问左子树，所以先将根节点保存起来
                    stack.push(head);
                    // 然后将head指针指向当前节点的左子节点，准备访问左子树
                    head = head.left;
                } else {
                    // 如果当前节点head为空，说明已经遍历完左子树，此时从栈中弹出一个节点
                    head = stack.pop();
                    // 输出该节点的值，这是中序遍历中访问根节点的操作
                    System.out.print(head.val + " ");
                    // 然后将head指针指向当前节点的右子节点，准备访问右子树
                    head = head.right;
                }
            }
            // 在完成整棵树的中序遍历后，换行，使输出更美观
            System.out.println();
        }
    }

    // 后序打印所有节点，非递归版
    // 这是用两个栈的方法
    public static void posOrderTwoStacks(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                collect.push(head);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                System.out.print(collect.pop().val + " ");
            }
            System.out.println();
        }
    }



    // 后序打印所有节点，非递归版
    // 这是用一个栈的方法
    public static void posOrderOneStack(TreeNode h) {
        // 如果根节点h不为空，则进行后序遍历
        if (h != null) {
            // 创建一个存储TreeNode类型的栈
            Stack<TreeNode> stack = new Stack<>();
            // 将根节点h压入栈中，作为遍历的起始点
            stack.push(h);
            // 如果始终没有打印过节点，h就一直是头节点
            // 一旦打印过节点，h就变成打印节点
            // 之后h的含义 : 上一次打印的节点
            while (!stack.isEmpty()) {
                // 获取栈顶元素，但不弹出，将其赋值给cur
                TreeNode cur = stack.peek();
                // 检查当前节点cur的左子节点情况
                if (cur.left != null && h != cur.left && h != cur.right) {
                    // 如果当前节点有左子树，并且上一次打印的节点不是当前节点的左子节点和右子节点（表示左子树还未处理）
                    // 则将当前节点的左子节点压入栈中，因为后序遍历先处理左子树
                    stack.push(cur.left);
                } else if (cur.right != null && h != cur.right) {
                    // 如果当前节点有右子树，并且上一次打印的节点不是当前节点的右子节点（表示右子树还未处理）
                    // 则将当前节点的右子节点压入栈中，因为后序遍历先左后右再根，右子树在左子树之后处理
                    stack.push(cur.right);
                } else {
                    // 左树、右树 没有 或者 都处理过了
                    // 此时可以打印当前节点的值，因为按照后序遍历的顺序，当前节点的左子树和右子树都已经处理完
                    System.out.print(cur.val + " ");
                    // 将栈顶元素弹出，并将弹出的节点赋值给h，表示上一次打印的节点
                    h = stack.pop();
                }
            }
            // 在完成整棵树的后序遍历后，换行，使输出更美观
            System.out.println();
        }
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);
        preOrder(head);
        System.out.println("先序遍历非递归版");
        inOrder(head);
        System.out.println("中序遍历非递归版");
        posOrderTwoStacks(head);
        System.out.println("后序遍历非递归版 - 2个栈实现");
        posOrderOneStack(head);
        System.out.println("后序遍历非递归版 - 1个栈实现");
    }

    // 用一个栈完成先序遍历
    // 测试链接 : https://leetcode.cn/problems/binary-tree-preorder-traversal/
    public static List<Integer> preorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                ans.add(head.val);
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        return ans;
    }

    // 用一个栈完成中序遍历
    // 测试链接 : https://leetcode.cn/problems/binary-tree-inorder-traversal/
    public static List<Integer> inorderTraversal(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    ans.add(head.val);
                    head = head.right;
                }
            }
        }
        return ans;
    }

    // 用两个栈完成后序遍历
    // 提交时函数名改为postorderTraversal
    // 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    public static List<Integer> postorderTraversalTwoStacks(TreeNode head) {
        List<Integer> ans = new ArrayList<>();
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                collect.push(head);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                ans.add(collect.pop().val);
            }
        }
        return ans;
    }

    // 用一个栈完成后序遍历
    // 提交时函数名改为postorderTraversal
    // 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    public static List<Integer> postorderTraversalOneStack(TreeNode h) {
        List<Integer> ans = new ArrayList<>();
        if (h != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(h);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.peek();
                if (cur.left != null && h != cur.left && h != cur.right) {
                    stack.push(cur.left);
                } else if (cur.right != null && h != cur.right) {
                    stack.push(cur.right);
                } else {
                    ans.add(cur.val);
                    h = stack.pop();
                }
            }
        }
        return ans;
    }

}